# 力扣28. 找出字符串中的第一个子字符串.py（来源：力扣）
# 给定一个字符串 haystack 和一个字符串 needle，在 haystack 中找出 needle 的第一个出现的位置 (从 0 开始)。 
# 如果不存在，则返回 -1。
def solve(haystack, needle):
    if not needle:
        return 0

    # KMP 算法实现 aabaaf
    def build_lps(pattern):
        lps = [0] * len(pattern)  # 初始化LPS表，长度与模式串相同，初始值全为0
        j = 0  # j表示前缀的长度
        i = 1  # i从1开始，因为LPS表的第一个值总是0

        while i < len(pattern):
            if pattern[i] == pattern[j]:  # 如果当前字符与前缀字符匹配
                j += 1  # 前缀长度加1
                lps[i] = j  # 更新LPS表
                i += 1  # 移动到下一个字符
            else:
                if j != 0:  # 如果前缀长度不为0
                    j = lps[j - 1]  # 回溯到前一个最长相同前后缀的位置
                else:
                    lps[i] = 0  # 如果前缀长度为0，LPS表当前位置为0
                    i += 1  # 移动到下一个字符
        return lps  # 返回构建好的LPS表

    lps = build_lps(needle)
    i = j = 0  # i - haystack, j - needle

    while i < len(haystack):
        if haystack[i] == needle[j]:
            i += 1
            j += 1
        if j == len(needle):
            return i - j  # 返回第一个匹配的起始位置
        elif i < len(haystack) and haystack[i] != needle[j]:
            if j != 0:
                j = lps[j - 1]  # 回溯
            else:
                i += 1
    return -1  # 未找到

if __name__ == "__main__":
    result = solve("aabaabaaf", "aabaaf")  # 使用样例数据调用函数
    # result = "aabaabaaf".find("aabaaf")
    print(result)  # 输出 2
